/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/largest-plus-sign
   @Language: C++
   @Datetime: 19-05-29 10:26
   */

// Method 1, DP, Time O(n*n), Space O(n*n), Time 151ms
class Solution {
public:
	/**
	 * @param N: size of 2D grid
	 * @param mines: in the given list
	 * @return: the order of the plus sign
	 * Tips:
	 * dp[i][j] means from (i,j) to left/right/up/down max length.
	 */
	int orderOfLargestPlusSign(int N, vector<vector<int> > &mines) {
		// Write your code here
		vector<vector<bool> > matrix(N,vector<bool>(N,true));
		for(const auto &v:mines)
			matrix[v[0]][v[1]]=false;
		vector<vector<int> > dp(N,vector<int>(N,0));
		int res=0;
		for(int i=0; i<N; ++i){
			for(int j=0, len=0; j<N; ++j){
				len=matrix[i][j]?len+1:0;
				dp[i][j]=len;
			}
			for(int j=N, len=0; j--;){
				len=matrix[i][j]?len+1:0;
				dp[i][j]=min(dp[i][j],len);
			}
		}
		for(int j=0; j<N; ++j){
			for(int i=0, len=0; i<N; ++i){
				len=matrix[i][j]?len+1:0;
				dp[i][j]=min(dp[i][j],len);
			}
			for(int i=N, len=0; i--;){
				len=matrix[i][j]?len+1:0;
				dp[i][j]=min(dp[i][j],len);
				res=max(res,dp[i][j]);
			}
		}
		return res;
	}
};

// Method 2, DP, Time O(n*n), Space O(n*n), Time 101ms
class Solution {
public:
	/**
	 * @param N: size of 2D grid
	 * @param mines: in the given list
	 * @return: the order of the plus sign
	 */
	int orderOfLargestPlusSign(int N, vector<vector<int> > &mines) {
		// Write your code here
		vector<vector<int> > dp(N,vector<int>(N,N));
		for(const auto &v:mines)
			dp[v[0]][v[1]]=0;
		for(int i=0; i<N; ++i){
			int l=0, r=0, u=0, d=0;
			for(int j=0, k=N-1; j<N && k>-1; ++j, --k){
				dp[i][j]=min(dp[i][j], l=(dp[i][j]?l+1:0));
				dp[i][k]=min(dp[i][k], r=(dp[i][k]?r+1:0));
				dp[j][i]=min(dp[j][i], u=(dp[j][i]?u+1:0));
				dp[k][i]=min(dp[k][i], d=(dp[k][i]?d+1:0));
			}
		}
		int res=0;
		for(int i=0; i<N; ++i)
			for(int j=0; j<N; ++j)
				res=max(res,dp[i][j]);
		return res;
	}
};
